import java.util.HashMap;

/**
 * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
 */

public class Solution_03 {

    public int lengthOfLongestSubstring(String s) {
        if (s == null) return 0;
        char[] chars = s.toCharArray();
        if (chars.length == 0) return 0;

        // 保存每一个字符最后一次出现的位置
        int[] prevIndex = new int[128];
        for (int i = 0; i < 128; i++) {
            prevIndex[i] = -1;
        }

        // 初始化第一个字符串的位置
        prevIndex[chars[0]] = 0;
        // 以前一个字符结尾的不重复子串开始的位置
        int li = 0;
        // 不重复子串的最大长度
        int max = 1;
        for (int i = 1; i < chars.length; i++) {
            // i位置字符上一次出现的位置
            int pi = prevIndex[chars[i]];
            if (li <= pi) {
                // 只有这一种情况更新li
                li = pi + 1;
            }
            // 更新i字符的位置
            prevIndex[chars[i]] = i;
            // 计算最大长度
            max = Math.max(max,i - li + 1);
        }
        return max;
    }

    /**
     * 方法二
     */
    public int lengthOfLongestSubstring1(String s) {
        //创建HashMap，Key用来存字符，Value用来存当前位置
        HashMap<Character,Integer> map = new HashMap<>();
        int max = 0;

        //利用快慢指针从头开始扫描
        for (int i = 0, j = 0; j < s.length(); j++) {
            //map中存在这个字符
            if (map.containsKey(s.charAt(j))) {
                //如果之前出现过这个字符，变换慢指针i的位置
                //要么不变，要么与之相同的且在前面出现过的字符后一个的位置
                i = Math.max(i,map.get(s.charAt(j)) + 1);
            }
            //将新的字符存入map中
            map.put(s.charAt(j),j);
            max = Math.max(max,j - i + 1);
        }
        return max;
    }

     /*方法一,自己曾今写的
    public int lengthOfLongestSubstring(String s) {
        if (s.length()==0){
            return 0;
        }
        if (s.length()==1){
            return 1;
        }
        int start = 0,end = 1;
        //要返回的结果
        int maxNum = 1;
        //被检查的字符串preStr
        String preStr = s.substring(0,1);
        //偏移位置
        int positon = 0;
        //进行比较的字符
        char c = s.charAt(end);
        int curLength = 0;
        while (end<s.length()){
            //不存在
            if (preStr.indexOf(String.valueOf(c)) == -1){
                end++;
                if (end<s.length()){
                    c = s.charAt(end);
                }
                curLength = end - start;
                String str = s.substring(start,end);
                preStr = s.substring(start,end);
            }else {
                //存在
                int index = preStr.indexOf(Character.toString(c));
                positon = positon + index + 1;
                start = positon;
                end++;
                if (end<s.length()){
                    c = s.charAt(end);
                }
                preStr = s.substring(start, end);
                maxNum = curLength > maxNum ? curLength : maxNum;
            }
            maxNum = curLength > maxNum ? curLength : maxNum;
        }
        return maxNum;
    }
    */
}
